ftp.mactech.com 2010/ftp.mactech.com.tar/ftp.mactech.com/challenge/13.06/ChallengeHexGame.sit/Challenge, Hex Game/Dynamic Memory4.c

Text File | 1997-05-07 | 5KB | 204 lines

typedef struct Header
{
    long
        size;    // the size in bytes of the block

    struct Header
        *prev,    // the previous block's header
        *next;    // the next block's header
} Header;

void InitializeHeap(Header *heapStart, long size);
void ChopBlock(Header *theBlock, long fragSize);
void *AllocateBlock(long size);
void FuseBlocks(Header *block);
void FreeBlock(void *data);
void HeapSummary(void);
Boolean IsPointerValid(void *data);
void SetHeap(Header *start);
Header *GetHeap(void);

Header
    *gHeapStart;

long
    gFreeBlocks,
    gUsedBlocks,
    gFreeSpace,
    gUsedSpace,
    gTotalSpace;


void InitializeHeap
(
    // these are assumed to be valid; no error-checking is performed
    Header *heapStart,    // the address of the start of the heap zone
    long    size        // the size of the zone
)
{
    heapStart->size = size - sizeof (Header);    // mark the size of the zone
    heapStart->prev = nil;                        // mark as being the first block…
    heapStart->next = nil;                        // …and the last
    gHeapStart = heapStart;                        // initialize the global heap start pointer
}

void ChopBlock
(
    // these are assumed to be valid; fragSize must be less than theBlock->size
    Header *theBlock,    // the block to chop
    long fragSize        // the size of the first new fragment
)
{
    Header
        *newBlock;

    newBlock = (Header *) (((char *) theBlock) + sizeof (Header) + fragSize);
    newBlock->size = theBlock->size - fragSize - sizeof (Header);    // the remaining space
    newBlock->prev = theBlock;    // newBlock comes after theBlock
    newBlock->next = theBlock->next;    // it gets inserted between theBlock and theBlock->next
    if (theBlock->next)
        theBlock->next->prev = newBlock;
    theBlock->size = fragSize;    // theBlock gets just what was asked for
    theBlock->next = newBlock;    // its new next block is newBlock
}

void *AllocateBlock
(
    long    size        // the size of the desired block
)
{
    const long
        BLOCK_IN_USE_MASK = 0x80000000, // if this bit is set in the 'size' field,
                                        // the block is in use
        MIN_BLOCK_SIZE = 80;            // the smallest usable block (board data + pointers)

    Header
        *currentBlock;    // a pointer to the block currently being considered

    currentBlock = gHeapStart;

    // loop until either there are no more blocks or a fitting one is found
    while (currentBlock && ((currentBlock->size & BLOCK_IN_USE_MASK) || (currentBlock->size < size)))
        currentBlock = currentBlock->next;

    if (currentBlock)    // a valid block was found
    {
        // if the block is much bigger than needed
        if ((currentBlock->size - size) > (MIN_BLOCK_SIZE + sizeof (Header)))
            ChopBlock(currentBlock, size);    // cut off a piece of exactly the right size
        currentBlock->size |= BLOCK_IN_USE_MASK;    // mark as being in use

        // return a pointer to just after the block header
        return (char *) (currentBlock + 1);
    }
    else
        // indicate that allocation failed
        return nil;
}

void FuseBlocks
(
    Header *block    // the block to fuse with its following neighbor
)
{
    Header
        *neighbor;

    neighbor = block->next;
    block->next = neighbor->next;
    neighbor->next->prev = block;
    block->size += sizeof (Header) + neighbor->size;    // blocks must not be in use
}

void FreeBlock
(
    void
        *data    // the block of data to free, fusing with its neighbors if possible
)
{
    const long
        BLOCK_IN_USE_MASK = 0x80000000;    // bit in size field used to indicate use of blocks

    Header
        *theBlock;        // the data block's header

    // the header is located just before the data
    theBlock = ((Header *) data) - 1;

    // assumed to be in use, with flag set; here it is reset
    if (theBlock->size & BLOCK_IN_USE_MASK)
        theBlock->size -= BLOCK_IN_USE_MASK;

    // if there is a next block and it is free
    if (theBlock->next && !(theBlock->next->size & BLOCK_IN_USE_MASK))
        FuseBlocks(theBlock);

    // if there is a previous block and it is free
    if (theBlock->prev && !(theBlock->prev->size & BLOCK_IN_USE_MASK))
        FuseBlocks(theBlock->prev);

}

void HeapSummary
(
    void
)
{
    const long
        IN_USE_MASK = 0x80000000;

    Header
        *block;

    block = gHeapStart;
    while (block->next)
        block = block->next;

    gFreeBlocks = gUsedBlocks = gFreeSpace = gUsedSpace = 0;

    while (block)
    {
        if (block->size & IN_USE_MASK)
        {
            gUsedBlocks++;
            gUsedSpace += block->size - IN_USE_MASK;
        }
        else
        {
            gFreeBlocks++;
            gFreeSpace += block->size;
        }
        block = block->prev;
    }
    gTotalSpace = (gFreeBlocks + gUsedBlocks) * sizeof (Header) + gFreeSpace + gUsedSpace;
}

Boolean IsPointerValid(void *data)
{
    Header
        *theBlock,
        *compBlock;

    theBlock = ((Header *) data) - 1;
    compBlock = gHeapStart;

    while(compBlock && compBlock != theBlock)
        compBlock = compBlock->next;

    if (compBlock == theBlock)
        return true;
    else
        return false;

}

void SetHeap(Header *start)
{
    gHeapStart = start;
}

Header *GetHeap(void)
{
    return gHeapStart;
}